package LeetCode._02算法基础.day09递归回溯;

import org.junit.Test;
import 题组.Solution;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 20 - 16:57
 * @Description 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * @Version 中等
 */
public class _78子集 {
    static int[] nums = {1, 2, 3};
    @Test
    public void test(){
        List<List<Integer>> res = subsets1(nums);
        System.out.println(res);
    }
    /* by me 递归回溯 */
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public void dfs(int[] nums, int i){
        if(i == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        //不取
        dfs(nums, i + 1);
        //取
        temp.add(nums[i]);
        dfs(nums, i + 1);
        //回溯
        temp.remove(temp.size() - 1);
    }

    /*官方思路*/
    //迭代法实现子集枚举
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();


    /*
    123 为例：

    000--[]
    001--[1]
    010--[2]
    011--[1,2]
    100--[3]
    101--[1,3]
    110--[2,3]
    111--[1,2,3]
     */
    public List<List<Integer>> subsets1(int[] nums) {
        int n = nums.length;
        //枚举二进制
        for (int mask = 0; mask < (1 << n); ++mask) {
            //每次清空，复用
            t.clear();
            for (int i = 0; i < n; ++i) {
                //二进制位1的位置添加对应的数
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<>(t));
        }
        return ans;
    }

}
